//
//  70_爬楼梯.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/3.
//

import UIKit

class ClimbStairs: NSObject {
    
    func QA() {
        let count = 6
        print(climbStairs(count), climbStairs1(count), climbStairs3(count))
    }
    
    func climbStairs(_ n: Int) -> Int {
        if n <= 2 {
            return n
        }
        return climbStairs(n - 1) + climbStairs(n - 2)
    }
    
    func climbStairs1(_ n: Int) -> Int {
        if n <= 2 {
            return n
        }
        var first = 1
        var second = 2
        var index = 3
        while index <= n {
            let temp = second
            second = second + first
            first = temp
            index += 1
        }
        return second
    }
    
    
    /// 动态规划实现
    func climbStairs3(_ n: Int) -> Int {
        if n <= 2 {
            return n
        }
        var dp = Array(repeating: 0, count: n + 1)
        dp[1] = 1
        dp[2] = 2
        for index in 3...n {
            dp[index] = dp[index - 1] + dp[index - 2]
        }
        return dp[n]
    }
}
